package com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.algorithms;

import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Edge;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Graph;
import com.liuzhilong.infrastructure.framework.algorithms.datastruct.graph.Vertex;
import lombok.AccessLevel;
import lombok.Getter;
import lombok.Setter;
import lombok.experimental.Accessors;

import java.util.*;

/**
 * <h1>深度优先-拓扑排序</h1>
 *
 * <p>
 *     拓扑排序是图中比较重要的一个算法。常常用于DAG图。像调度执行中，需要进行拓扑排序进行执行顺序的排序
 * </p>
 *
 * @param <T>
 */
public class DfsOrder<T> {

    @Setter(AccessLevel.PRIVATE)
    @Accessors(chain = true)
    private Graph<T> graph;

    private Set<Vertex<T>> visited = new HashSet<>();
    //前序
    @Getter
    private Deque<Vertex<T>> pre = new LinkedList<>();
    //后序
    @Getter
    private Deque<Vertex<T>> post = new LinkedList<>();
    //逆后序
    @Getter
    private Deque<Vertex<T>> reversePost = new LinkedList<>();

    /**
     * 初始化
     */
    private DfsOrder<T> init(){
        this.graph.getVertices().forEach((key,value)->this.dfs(value));
        return this;
    }


    /**
     * <h1>DFS遍历排序<h1/>
     *
     * <p>
     *     dfs的过程就是由一个顶点开始，遍历图的过程。
     *
     * </p>
     * @param vertex
     */
    private void dfs(Vertex<T> vertex){
        //退出条件

        if (visited.contains(vertex)) {
            return;
        }
        //先访问的在前
        pre.offer(vertex);
        visited.add(vertex);
        if(vertex.getNext()!=null){
            for(Edge<T> edge:vertex.getNext()){
                dfs(edge.getTo());
            }
        }
        //先访问的在后面
        post.offer(vertex);
        /**
         * 拓扑排序
         *
         * 将一个图的顶点排序，使得顶点的指向永远是向下的。
         * dfs遍历中，在递归遍历之后，将顶点压入栈中。这样能保证，先访问的顶点排在前面。当遍历完之后，栈中保存的顺序就是拓扑排序的顺序。
         */
        reversePost.push(vertex);
    }


    public static final <TT> DfsOrder<TT> create(Graph<TT> graph) {
        return new DfsOrder<TT>().setGraph(graph).init();
    }





}
